# 84/100 动态规划-零钱兑换
# leetcode第322题: https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/24
import math
from functools import cache

from leetcode import test


def coinChange(coins: list[int], amount: int) -> int:
    """动态规划， 我的方法"""
    if amount == 0:
        return 0
    if min(coins) > amount:
        return -1
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for j in coins:
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1


def coinChange_opt(coins: list[int], amount: int) -> int:
    """优化的dp方法，可以减少一个条件的判断"""
    if amount == 0:
        return 0
    if min(coins) > amount:
        return -1
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1


def coinChange_ultra(coins: list[int], amount: int) -> int:
    """一个非常巧妙的方法

    << 操作符
    左移运算，将一个数的二进制表示向左移动指定的位数。如：
    x = 5  # 二进制为: 00000101
    result = x << 3  # 左移 3 位
    print(result)  # 输出: 40 等价于 x * 2^3
    常用 << 快速进行乘法运算

    |= 操作符
    按位或赋值，逐位比较两数，并在每一位上取或运算的值
    x = 5   # 二进制为: 00000101
    y = 3   # 二进制为: 00000011
    x |= y  # 按位或后赋值给 x
    # 结果为: 00000111 (十进制为 7)
    常用于合并标志位、状态标识或路径状态更新

    举例
    coins = [1, 2, 5]
    amount = 5

    初始状态:
        step = 0
        path = 1 << 5 = 100000

    第一次循环:
        用硬币 1: path >> 1 = 010000，合并后 temp = 110000
        用硬币 2: path >> 2 = 001000，合并后 temp = 111000
        用硬币 5: path >> 5 = 000001，合并后 temp = 111001
        更新 path = temp = 111001
        step = 1

    终止条件：
        path & 1 = 1，找到组合。
    """
    # step表示当前所需的最小硬币数量
    # path使用二进制位表示状态。1 << amount 将目标金额位置为 1，其他位为 0。
    # 如果amount=5，则 path 的二进制位为 100000
    step, path = 0, 1 << amount
    while path & 1 != 1:  # 终点判定 检查最低位（金额 0）是否为 1。如果为 1，说明已经找到硬币组合使得金额为 amount。
        temp = path  # temp表示当前可以达成的金额集合
        for coin in coins:
            # 将 path 右移 coin 位，表示用该面值的硬币从现有状态进行扩展。
            # 如果当前 path 是 100000（即金额 5），用面值 2 的硬币，右移 2 位得到 001000（即金额 3）。
            # |= 是按位“或”操作，相当于将可以达成的所有金额标记为 1。temp 就是 101000
            temp |= path >> coin
        if path == temp:  # 如果temp与path相同表示无法凑出该币值
            return -1
        path |= temp
        step += 1
    return step


if __name__ == '__main__':
    inp = [{"coins": [1, 2, 5], "amount": 11}, {"coins": [2], "amount": 3}, {"coins": [1], "amount": 0},
           {"coins": [2], "amount": 1}, ]
    out = [3, -1, 0, -1]

    test.test_function(coinChange, inp, out)
    test.test_function(coinChange_opt, inp, out)
    test.test_function(coinChange_ultra, inp, out)
